In networks such as mesh type networks, there are numerous possible routes for passing communication between one node and another node. Many types of routing algorithms are known for finding the shortest route, or for making best use of available capacity. One particular case, or application of routing methods is for the purpose of restoring a network after a failure has been detected. Such a failure may take the form of loss of a link between nodes, or loss of a node. Methods of restoring the network can be categorised as preplanned, or adaptive. Preplanned methods require knowledge of the topology of the network. Adaptive methods involve finding out the topology of the network around the failure, in real time. This involves making use of some processing capability at the nodes.
Conventional methods may involve distributed processing at the nodes, or centralised control by a remote processing means.
Conventionally, there have been three main characteristics by which restoration methods have been assessed. Firstly the percentage of the capacity of the failed link which is restored using the alternative routes, can be measured. Secondly, the length of the alternative routes can be measured (shorter routes are preferred usually). Thirdly, the time taken to identify and establish the alternative routes can be assessed.
Clearly, the performance of a restoration method depends crucially on how much spare capacity there is in the alternative routes. If the alternative routes are heavily loaded already and have little spare capacity, then more such alternative routes will be needed, and they are likely to be longer.
In one known algorithm (Grover WD "Self Healing Networks--a distributed algorithm for k-shortest link--disjoint paths in a multigraph with applications in real time network restoration, pages 76 to 106, PhD dissertation, University of Alberta, Autumn 1989), a completely distributed k-shortest paths processing sequence with no prior knowledge of network topology at any node, is disclosed. The process is shown in FIG. 1, steps 50 to 55. FIG. 2 shows in schematic form, the layout of the nodes involved in the process. FIG. 2 shows a relatively simple arrangement. In practice there are likely to be many nodes around the broken link, and many nodes in each route.
When a link failure occurs, two custodial nodes are cast at the end points of the failed link. Using their unique node identification numbers, they order themselves into sender 63 and chooser 64. The sender creates flooding instances which propagate from sender to chooser, for each failed channel, to search out available spare paths. The nodes involved in the search propagation, known as tandem nodes 65, assign spare channels to the flooding instances, and cause the flooding instances to increase their count of the number of hops used. When a chooser receives a flooding instance, it can read the hop count to identify the shortest route. The shortest route is acknowledged, and capacity assigned by the tandem nodes is relinquished unless it is on the acknowledged shortest route. The same process is carried out for each channel which uses the failed link.
Others have proposed variations on this basic algorithm, including the concept of multiple candidate choosers, as shown in "A Distributed Restoration Algorithm for a Multiple Link and Node Failures of Transport Networks" by H Komine et al (proceedings of the IEEE Globecom 1990, pages 459 to 463). Furthermore, in "Restoration Message Transfer Mechanism and Restoration Characteristics of Double Search Self Healing ATM Network", IEEE Journal of Select Areas in Communications, volume 12 number 1 pages 149 to 157, January 1994, there is disclosure of a double search. The sender and chooser take on each others roles, to enable searches in both directions.
However, such methods can result in a large number of search instances, if there are many channels. It is known to use only a single search instance between the sender and chooser, from "Self Healing Techniques Utilising Virtual Path Concept for ATM Networks", Kawamura et al, Electronics and Communication in Japan, part 1, volume 75, number 4, pages 86 to 96, 1992. However, this method involves the search instance obtaining information about capacity for groups of channels, on a channel by channel basis. Again, where there are many channels, the flooding instance will become large and complex.
With all the methods discussed, based on spare capacity being identified and allocated by each tandem node, on a channel basis, for example for each virtual path (VP) in an ATM system, the first virtual path may cause temporary allocation of spare capacity on a wide range of alternative routes, until the shortest route is acknowledged. Such temporary allocation may block a succeeding virtual path or force it to find a much longer route than would otherwise be necessary. Accordingly, performance of such restoration methods may be poor, particularly on networks such as wide area telecommunications networks which may be heavily loaded, and have little spare capacity.
It is also known to use complex max-flow algorithms at the network configuration or design stage, to calculate the minimum amount of spare capacity required to achieve 100% restoration of failures on neighbouring links or nodes. These enable performance testing of restoration algorithms, to see how close they come to optimal restoration. This is unrealistic because real networks are often so heavily loaded that 100% restoration is not possible. Therefore there is a need for algorithms better suited to such heavily loaded networks.